package cn.edu.xjtu.carlWay.stackAndQueue.topKFrequentElements;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 347. 前 K 个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        int[] nums = {6, 0, 1, 4, 9, 7, -3, 1, -4, -8, 4, -7, -3, 3, 2, -3, 9, 5, -4, 0};
        int[] ints = topKFrequent(nums, 6);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        ArrayList<Integer> array = new ArrayList<>();
        Map<Integer, Integer> freqMap = new HashMap<>();
        Map<Integer, Boolean> inArrayMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int freq = freqMap.getOrDefault(nums[i], 0) + 1;
            freqMap.put(nums[i], freq);
            getTopK(array, freqMap, inArrayMap, nums[i], k);
        }
        for (int i = 0; i < array.size(); i++) {
            ret[i] = array.get(i);
        }
        return ret;
    }

    public static void getTopK(ArrayList<Integer> array, Map<Integer, Integer> freqMap, Map<Integer, Boolean> inArrayMap, int num, int k) {
        if (inArrayMap.getOrDefault(num, false)) {
            // 当前元素已经在数组中
            int index = array.indexOf(num);
            int freq = freqMap.get(num);
            int insertIndex = 0;
            for (int i = index - 1; i >= 0; i--) {
                if (freqMap.get(array.get(i)) > freq) {
                    insertIndex = i + 1;
                    break;
                }
            }
            if (index != insertIndex) {
                array.add(insertIndex, num);
                array.remove(index + 1);
            }
        } else {
            // 当前元素不在数组中
            if (array.size() != k) {
                array.add(num);
                inArrayMap.put(num, true);
            } else if (freqMap.get(num) > freqMap.get(array.get(array.size() - 1))) {
                int freq = freqMap.get(num);
                int insertIndex = 0;
                for (int i = array.size() - 1; i >= 0; i--) {
                    if (freqMap.get(array.get(i)) > freq) {
                        insertIndex = i + 1;
                        break;
                    }
                }
                array.add(insertIndex, num);
                int ele = array.remove(k);
                inArrayMap.put(ele, false);
                inArrayMap.put(num, true);
            }
        }
    }
}
